1. Field of the Invention
The present invention relates to a genetic algorithm executing device and method for efficiently searching for a solution using a genetic algorithm (GA), and a program storage medium thereof.
2. Description of the Related Art
Genetic algorithms are application technologies inspired by mechanisms of inheritance and evolution of living things. In the evolution of living things, genomic changes like crossovers of chromosomes, mutations of genes, etc. may occur when new individuals (children) are born from old ones (parents). An individual which can not adapt to the environment fails to survive after natural selection on the other hand an adaptable one survives and becomes a parent of a new descendant. Such adaptability is determined by their genomic properties.
In a genetic algorithm, a candidate of solution to an optimization problem is represented as a character string (corresponding to a chromosome which is a one-dimensional string of genes), and a solution is searched by repeating genetic operations including selection, crossover, mutation, etc. In this specification, we use the word "character" not only in the sense of alphabets but also in the universal sense of numbers, symbols, . . . , etc.
Here, evolution of living things corresponds to a process in which a value of the objective function (which is the function evaluated to determine the suitability for the optimization problem) of each character string approaches an optimum value. The selection operation is performed by choosing parent strings with a high evaluation value (which is calculated by the objective function), as shown in FIG. 1A. In a mutation operation, some characters are replaced with other characters at random, as shown in FIG. 1B. In the crossover operation, substrings of a pair of strings are exchanged, as shown in FIG. 1C. By repeating these operations, we can obtain new strings that make the objective function more suitable than with the initial ones.
In the conventional genetic algorithm, mutation is performed uniformly in the whole the of string, i.e. over all positions in the string. However in many optimization problems, there are some positions that need not (or have to) be mutated. For such problems, the conventional uniform mutation is not efficient. Accordingly, we can barely obtain a solution by the conventional method, especially for large scale problems.
Furthermore, since a sufficiently large number of generations is required to obtain an adequate string by the conventional genetic algorithm, the search process is continued up to the designated generation, even if a solution has been obtained. The conventional method also has a problem of efficiency of calculation.